#include <bits/stdc++.h>

using namespace std;


struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};

class Solution1 {
    unordered_map<int,int> mp;
public:
    Solution1(){
        mp.clear();
    }
    ListNode* deleteDuplication(ListNode* pHead)
    {
        if(pHead==NULL) return NULL;
        ListNode *p=pHead,*q=pHead->next,*tmp=NULL;
        while(p){
            mp[p->val]++;
            p=p->next;
        }
        //去表头重复
        while(mp[pHead->val]>1){
            tmp=pHead;
            pHead=pHead->next;
            delete tmp;
            if(!pHead) return NULL;
        }

        p=pHead;
        while(p->next){
            q=p->next;
            if(mp[q->val]>1){
                tmp=q;
                p->next=q->next;
                delete tmp;
            }else{
                p=p->next;
            }
        }

        return pHead;
    }
};
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        ListNode *pre=NULL,*p=pHead,*q=NULL;
        while(p){
            if(p->next&&p->next->val==p->val){
                q=p->next;
                while(q && q->next&& q->next->val==p->val){
                    q=q->next;
                }
                if(p==pHead){
                    pHead=q->next;
                }else{
                    pre->next=q->next;
                }
                p=q->next;
            }else{
                pre=p;
                p=p->next;
            }
        }
        return pHead;
    }
};



/*
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 
例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
*/
ListNode * g(){
    ListNode *head,*p,*q;
    head=new ListNode(1);
    p=new ListNode(1);
    head->next=p;
    q=new ListNode(3);
    p->next=q;
    p=q;
    
    q=new ListNode(3);
    p->next=q;
    p=q;

     q=new ListNode(4);
    p->next=q;
    p=q;
     q=new ListNode(4);
    p->next=q;
    p=q;
    
    q=new ListNode(5);
    p->next=q;
    p=q;

    return head;

}   
void print(ListNode *head){
    ListNode *p=head;
    while(p){
            cout <<p->val <<" ";
            p=p->next;
        }cout <<endl;
}
int main(){
    Solution s;

    ListNode *p=g();
    print(p);
  

    ListNode *q=s.deleteDuplication(p);

    print(q);



    return 0;
}